# Definition for a binary tree node.
import collections
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        # if not root:
        #     return None
        # root.left, root.right = self.invertTree(root.right),self.invertTree(root.left)
        #
        # return root
#         非递归

        # if not root:
        #     return None
        # queue = collections.deque()
        # node = root
        # queue.append(node)
        # while queue:
        #     node = queue.pop()
        #     if node :
        #         if node.left or node.right:
        #             node.left,node.right = node.right,node.left
        #             queue.append(node.left)
        #             queue.append(node.right)
        # return root
        if root:
            self.invertTree(root.left)
            self.invertTree(root.right)
            root.left, root.right = root.right, root.left
            return root


m1 = TreeNode(1)
m1.left = TreeNode(2)
m1.right = TreeNode(3)
m1.right.left = TreeNode(3)
# m1.right.right = TreeNode(2)
s = Solution()

t = s.invertTree(m1)
print(t)
